package com.gxc.string;

/**
 * 将给定的数转换为字符串，原则如下:1对应 a，2对应b，·...26对应z，
 * 例如12258可以转换为
 * "abbeh"，“aveh”，“abyh”."Ibeh” 和“lyh"，个数为5，
 * 编写一个函数，给出可以转换的不同字符串的个数。
 */
public class NumberToCharacter {

    public static void main(String[] args) {
        int size = 10000;
        for (int i = 0; i < size; i++) {
            char[] number = random();
            if (process(number, 0) != Process(number, 0) ||
                    process(number, 0)!= dpProcess(number)) {
                for (int j = 0; j < number.length; j++) {
                    System.out.print(number[j] + "");
                }
                System.out.println("算法错误");
                break;
            }
        }
        System.out.println("跑完");
    }

    private static char[] random() {
        int size = (int) (100 * Math.random());
        char[] array = new char[size];
        for (int i = 0; i < array.length; i++) {
            int random = (int) (27 * Math.random());
            array[i] =  (char)('a' + random);
        }
        return array;
    }

    /**
     * 从前往后尝试
     * .......x.........y......
     * 0
     * 1-9
     * 10-19
     * 20-26
     *
     * @return
     */
    private static int process(char[] number, int index) {
        if (number == null || number.length ==0) return 1;
        //如果尝试已走完数字，则发现一例数可转换为字符串
        if (index == number.length) return 1;
        //总个数
        int sum = 0;
        if (number[index] == '0') return 0;
        else if (number[index] == '1') {
            //index 单独成为一个字符
            sum = process(number, index+1);
            //index + (index+1) 合并成为一个字符  10-19
            if (index+2<=number.length) sum += process(number, index+2);
        } else if (number[index] == '2'){
            //index 单独成为一个字符
            sum = process(number, index+1);
            //index + (index+1) 合并成为一个字符  20-26
            if (index+2<=number.length && number[index+1]<='6') sum += process(number, index+2);
        } else {
            sum = process(number, index+1);
        }
        return sum;
    }

    /**
     * 动态规划
     * 根据递归  index  依赖 index+1 index+2
     * 所以从后往前算值
     * @param number
     * @return
     */
    public static int dpProcess(char[] number) {
        if (number == null || number.length==0) return 1;
        if (number[0] == '0') return 0;

        int[] dp = new int[number.length+1];
        dp[number.length] = 1;
        for (int index = number.length-1; index >= 0; index--) {
            if (number[index] == '0')  dp[index] = 0;
            else if (number[index] == '1') {
                //index 单独成为一个字符
                dp[index] = dp[index+1];
                //index + (index+1) 合并成为一个字符  10-19
                if (index+2<=number.length) dp[index] += dp[index+2];
            } else if (number[index] == '2'){
                //index 单独成为一个字符
                dp[index] = dp[index+1];
                //index + (index+1) 合并成为一个字符  20-26
                if (index+2<=number.length && number[index+1]<='6')  dp[index] += dp[index+2];
            } else {
                dp[index] = dp[index+1];
            }
        }
        return dp[0];
    }

    //网上暴力递归
    private static int Process(char[] input, int index){
        //只有空串时会遇到这种情况，所以返回唯一的一种情况，空串
        if(index==input.length) return 1;
        //如果当前位置的值为0，则没办法转成任何字母
        if(input[index]=='0') return 0;

        int sum = 0;
        //此时该位置不为0 ，则肯定有结果。res的值为当前的解以及第index+1到最后的那一段字符串的结果的和
        sum = Process(input, index+1);
        //此时遇到了字符串的结尾，无法再继续往下递归了，因此染回结果res
        if(index==input.length-1) return 1;
        //如果当前位置和其后面的位置的数字组合不大于26，说明两个数可以组合出一种情况
        //此时res要加上index+2到结尾的情况
        if(((input[index]-'0')*10+input[index+1]-'0')<27)
            sum+=Process(input, index+2);

        return sum;
    }

}
